The present invention refers generally to graph partitioning, and more particularly, to partitioning a network of cells into disjoint blocks.
The problem of partitioning interconnected cells between limited resources is well known in the art. This problem arises in many areas. The task is to divide a number of cells, which have some type of interaction between them, among a number of resources. A goal is to minimize the cost of the interaction between the cells. The cost may be measured by a variety of values, depending upon the nature of the network. The cost of the interactions is often referred to as the cutsize.
For example, in the area of circuit partitioning for integrated circuits, discrete logic functions may be allocated to specific logic elements. The connections between different logic elements require the use of interconnect resources such as conductive wires. By minimizing the number of interconnections required between logic elements, the total number of wires needed for a particular design may be reduced. This allows a larger design to fit into a smaller area. The cost of this network may be measured by the number of interconnections needed.
Another area, for example, in which partitioning may be used is in parallel processing. Some parallel processing applications require that a large number of individual computations be assigned to a smaller number of processors. However, often the individual computations depend on results from other computations. This requires the processors to communicate. These communications slow down the speed in which the calculation can be completed. The cost of this network may be measured by the amount of time spent communicating. It is desirable to allocate the computations to processors such that the communication costs are minimal. Many other applications for this invention may be readily apparent to one skilled in the art.
The problem of graph partitioning has been extensively considered in the literature. See, for example, B. W. Kernighan and S. Lin, "An Efficient Heuristic Procedure For Partitioning Graphs", and Laura A. Sanchis, "Multiple-Way Network Partitioning", both of which are incorporated herein by reference for all purposes. Traditionally, in order to solve a network partitioning problem, the network has been described as a hierarchical graph. Each node in the graph represents a possible resource and each edge connecting the nodes represents a possible interconnection between the resources. The graph is a hierarchical graph wherein each node contains zero or more subnodes (its children or descendants) but can only be a descendant of one other node (its parent or ancestor.) The cells (i.e., those items which are to be assigned to the resources) are only placed in leaf nodes. Leaf nodes are those nodes at the lowest level of the graph. By definition, leaf nodes have no descendants.
A typical three-level hierarchical graph is depicted in FIG. 2. Each level of the graph depicts a different level of hierarchy. For example, in the case of circuit partitioning, the H.sub.0,0 node may refer to the entire network; whereas, the H.sub.2,0 node may be a particular group of logic elements within the network. The cells, for example cells a and b in the H.sub.2,0 node, may refer to particular logic elements. The subscripts in the node references are given to simplify discussion of particular nodes and are representative of the level of the node and a node number within that level.
As described above, the objective of partitioning is to place all the cells legally into the graph such that the interconnections among the nodes are minimized. This has traditionally been done using gain vectors. By this traditional method, a gain vector may be calculated for each possible move of each cell. A gain vector contains information of the change in number of interconnections (i.e., cutsize) in the graph due to moving a particular cell. A first entry in the gain vector represents the change in the cutsize that would be realized if the cell were moved. The second entry represents the likely change in cutsize from a subsequent cell move if the cell were moved now. For example, it assumes the current move has been made, and then determines what the next probable move would be and how that move will affect the cutsize. In other words, it does a lookahead estimation which predicts how future cell moves will be affected by moving the cell. The number of entries in the gain vector is dependant how many levels of lookahead are desired.
Values for the gain vectors are calculated and the cell with the best gain vector may be moved. The gain vectors are then recalculated and the procedure is repeated for the remaining cells. This may continue until a desirable partition is found. This method is described in the Sanchis reference cited above.
A limitation of the traditional method is that it does not take into account the effect at all hierarchal levels. It is only a two level approach and therefore will not find the move that will be the best from a global standpoint. It is therefore desirable to find a method which will place all cells into a block such that the costs are minimized for all levels of the design. An improved method for graph partitioning is therefore desirable.